FIG. 1 depicts a portion of a conventional network 10. The conventional network 10 includes nodes 12, 14, 16, 18, 20 and 22. The nodes 12, 14, 16, 18, 20 and 22 are connected by links 24, 26, 28, 30, 32, 34, 36 and 38. Although only six nodes 12, 14, 16, 18, 20 and 33 and eight links 24, 26, 28, 30, 32, 34, 36 and 38 are shown, a conventional network 10 typically includes a larger number of nodes and links. A particular link 24, 26, 28, 30, 32, 34, 36 and 38 is typically designated using the nodes 12, 14, 16, 18, 20 and 22 to which the link 24, 26, 28, 30, 32, 34, 36 and 38 is attached. For example, the link 24 is typically designated as link AB 24 because the link 24 links node A 12 with node B 14. However, for clarity, the links 24, 26, 28, 30, 32, 34, 36 and 38 will merely be designated by their numbers. Typically, users of the network have computer systems (not explicitly shown) that are coupled with one of the nodes 12, 14, 16, 18, 20 and 22. The nodes 12, 14, 16, 18, 20 and 22 may thus be routers for the network 10.
Each link 24, 26, 28, 30, 32, 34, 36 and 38 is used to allow traffic to flow through the network 10 between the nodes 12, 14, 16, 18, 20 and 22. Traffic travels through the network in flows. A flow can be viewed as a time sequence of datagrams from one input to one output. The input will be termed a source node while the output will be called the destination node. The sequence of links and nodes used in a flow is the path of the flow. Each flow typically passes through multiple nodes 12, 14, 16, 18, 20 or 22 and links 24, 26, 28, 30, 32, 34 and 36 between the source node and destination node. Each link 24, 26, 28, 30, 32, 34 and 36 includes multiple flows. In addition each link 24, 26, 28, 30, 32, 34 and 36 has a particular capacity, depicted in FIG. 1. For example, the capacity of the link 24 is five megabits per second (“Mb/sec”), while the capacity of the link 26 is six Mb/sec. One criterion for traffic from through the network 10 is that the bandwidths for the flows through a particular link 24, 26, 28, 30, 32, 34 and 36 not exceed the capacity of the link 24, 26, 28, 30, 32, 34 and 36. The bandwidth of a flow is the rate of the flow (generally somehow averaged over time) in bits per second through a particular component of the network 10.
In order to route data between different users of the network 10, a path through the network 10 must be selected. For example, suppose a user having a computer system coupled to the node A 12 sends a message to a user having a computer system coupled to the node F 16. Thus, node A 12 is the source node (node at which the message originates), while node F is the destination node (node at which the message is desired to terminate). There are many different paths through the network 10 that such a message could take. For example, the message could go from node A 12 through link 24 to node B 14, then through link 30 to node F. Similarly, the message could go from node A 12 through link 26 to node C 18, through link 34 to node E 22, through link 32, ending at node F 16. There are other possible paths for a message to take between the source node A 12 and the destination node F 16.
In order to select a path from the possible paths, a conventional routing protocol, or path selection method, is typically used. FIG. 2 depicts a conventional method 50 for selecting the path. The conventional method 50 uses a conventional open shortest path first (“OSPF”) routing protocol. OSPF was developed for Internet protocol (“IP”) networks by the interior gateway protocol (“IGP”) for the Internet Engineering Task Force (“IETF”) (see IETF RFC 1247). Currently, different versions of OSPF are used in conventional routing. The shortest path in OSPF is the path that has the minimum cost. The path having the minimum cost is the path through links having the largest available bandwidth. In addition, OSPF and the conventional method 50 use Dijkstra's algorithm, which computes a running cost for different alternate paths simultaneously. The path having the minimum cost is selected for transmission of data from the source node to the destination node.
Thus in the conventional method 50, a first node, or source node, is considered to be the current node, via step 52. The cost for each link coupled to the current node is calculated. To do so, the sum of the actual bandwidths for flows currently through each of the links coupled to the current node is calculated, via step 54. Thus, step 54 calculates the amount of traffic through each of the links coupled with the current node. The available bandwidth for each link coupled to the current node is then determined, via step 56. The available bandwidth for a link is the capacity of the link minus the sum of the bandwidths of flows currently or recently through the link. Thus, the available bandwidth is a measure of the space that a link currently has available to accommodate another flow. The link having the greatest available bandwidth is the link which has the lowest cost. Therefore, step 54 and 56 determine the link having the lowest cost. The link which has the lowest cost is then selected to be part of the path, via step 58. It is then determined whether the destination node has been reached, via step 60. If the destination node has not been reached, then the node at the other end of the link selected in step 58 is designated as the current node, via step 62. The method 50 then determined to step 54. If, however, the destination now has been reached, then the path is defined as the path which includes all the links selected in step 58 and the corresponding nodes.
For example, referring to FIGS. 1 and 2, suppose a path between the node A 12 and node F 16 is decided to be determined. The suppose that each of the links 24, 26, 28, 30, 32, 34, 36 and 38 is currently carrying a total of 4 Mb/sec for flows that are already existing. Thus, for ease of explanation, each of the links 24, 26, 28, 30, 32, 34, 36 and 38 is assumed the carrying the same amount of traffic. However, typically this is not the case. Using OSPF of the conventional method 50, the node A 12 and is the first current node designated step 52. The sum of the actual bandwidths for flows for each of the links 24 and 26 is 4 Mb/sec. The links 26 and 24 have capacities of six and five Mb/sec, respectively. Thus, the available bandwidth for the link 26 is two Mb/sec while the available bandwidth for the link 24 is one Mb/sec. Thus, the link 26 will be selected as part of the path. Because the destination is not been reached, the node C 18 is designated as the current node. When the steps 54 through 56 are performed for the links 28, 34 and 36, the link having the highest available bandwidth will be determined to be the link 34. Thus, the link 34 will be part of the path. Because the destination has not yet been reached, the node E 22 will be designated as the current node. The link having the highest available bandwidth from node E 22 is the link 32. Thus, the path from the node A 12 to the node F 16 is through link 26 to node C 18, then through link 34 to node E 22, then through the link 32 to the destination node F 16.
A relatively new development in managing traffic through network is DiffServ. DiffServ is an emerging IETF standard for providing differentiated services (see IETF RFC 2475 and related RFCs). Differentiated services are also described by RFC 2212 Specification of Guaranteed Quality of Service. S. Shenker, C. Partridge, R. Guerin. September 1997. (Format: TXT=52330 bytes) (Status: PROPOSED STANDARD), RFC 2474 Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers. K. Nichols, S. Blake, F. Baker, D. Black. December 1998. (Format: TXT=50576 bytes) (Obsoletes RFC1455, RFC1349) (Status: PROPOSED STANDARD), RFC 2475 An Architecture for Differentiated Service. S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, W. Weiss. December 1998. (Format: TXT=94786 bytes) (Status: INFORMATIONAL), RFC 2750 RSVP Extensions for Policy Control. S. Herzog. January 2000. (Format: TXT=26379 bytes) (Updates RFC2205) (Status: PROPOSED STANDARD), RFC 2983 Differentiated Services and Tunnels. D. Black. October 2000. (Format: TXT=35644 bytes) (Status: INFORMATIONAL) and related RFCs. Differentiated services allow different flows to be provided with varying service. For example, a client may pay to have some guaranteed minimum amount of bandwidth (relatively expensive per bit per second) and some additional bandwidth if available up to a maximum rate (relatively inexpensive per bit per second). Thus, DiffServ allows a minimum guaranteed bandwidth to be set for each flow.
OSPF results in a path between the source node and the destination node even when differentiated services are provided. However, one of ordinary skill in the art will readily realize that the conventional method 50 does not take into account some of information used in providing differentiated services. Instead, paths are allocated to the based only on the traffic currently were recently through a particular link. The paths would thus be allocated without accounting for the minimum guaranteed bandwidths for existing flows already through the network 10. Thus, the path determined using the conventional method 50 when differentiated services are allowed may not be a path which allocates bandwidth in an optimal manner. For example, a path for a flow having a particular minimum guaranteed bandwidth might not include certain links because these links have a high current or recent flow. The large current or recent flow may be due to other flows which have high current bandwidths (for example because there was a large amount of excess bandwidth in the link that was allocated to the flows), but low minimum guaranteed bandwidths. Because the link is not included in the path, bandwidth in the link may not be allocated to the new flow even though it might be desirable to do so.
Accordingly, what is needed is a system and method for allocating bandwidth in links and, therefore, determining paths in a manner which better accounts for differentiated services. The present invention addresses such a need.